package leetcode.editor.cn;

//给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 
//
// 整数除法仅保留整数部分。 
//
// 你可以假设给定的表达式总是有效的。所有中间结果将在 [-2³¹, 2³¹ - 1] 的范围内。 
//
// 注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "3+2*2"
//输出：7
// 
//
// 示例 2： 
//
// 
//输入：s = " 3/2 "
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：s = " 3+5 / 2 "
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 3 * 10⁵ 
// s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开 
// s 表示一个 有效表达式 
// 表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内 
// 题目数据保证答案是一个 32-bit 整数 
// 
// Related Topics 栈 数学 字符串 👍 550 👎 0

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

//Java：【227】 - 基本计算器 II
public class BasicCalculatorIi_227{
    public static void main(String[] args) {
        Solution solution = new BasicCalculatorIi_227().new Solution();
                // TO TEST
        System.out.println(Integer.MAX_VALUE);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int calculate(String s) {
        char[] chars = s.toCharArray();
        Stack<Integer> nums = new Stack<>();
        int num =0;
        char preOperation = '+';
        for(int i=0;i<chars.length;i++){
            char ch = chars[i];
            if(Character.isDigit(chars[i])){
                num = num*10+ch-'0';
            }
            if(!Character.isDigit(ch) && ch!=' ' || i==chars.length-1){
                switch(preOperation){
                    case '+':
                        nums.push(num);
                        break;
                    case '-':
                        nums.push(-num);
                        break;
                    case '*':
                        nums.push(nums.pop()*num);
                        break;
                    case '/':
                        nums.push(nums.pop()/num);
                        break;
                }
                preOperation=ch;
                num=0;
            }
        }
        int res=0;
        while (!nums.isEmpty())
            res+=nums.pop();
        return res;
    }

    public int cal(int tmp2, int tmp1, char operation){
        if(operation=='+') return tmp1+tmp2;
        else if(operation=='-') return tmp2-tmp1;
        else if(operation=='*') return tmp1*tmp2;
        else return tmp1/tmp2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 我的思路
     * @param s
     * @return
     */
    public int calculate(String s) {
        char[] chars = s.toCharArray();
        Deque<Integer> nums = new LinkedList<>();
        Deque<Character> operations = new LinkedList<>();
        boolean lastIsNum=false;
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            switch (ch) {
                case '+':
                case '-':
                case '*':
                case '/':
                    if(!operations.isEmpty() && (operations.peekLast() =='*' || operations.peekLast()=='/'))
                        nums.addLast(cal(nums.pollLast(), nums.pollLast(), operations.pollLast()));
                    lastIsNum=false;
                    operations.addLast(ch);
                    break;
                case ' ':
                    break;
                default:
                    if(lastIsNum) nums.addLast(nums.pollLast()*10+ch-'0');
                    else nums.addLast(ch-'0');
                    lastIsNum=true;
            }
        }
        if(!operations.isEmpty() && (operations.peekLast() =='*' || operations.peekLast()=='/'))
            nums.addLast(cal(nums.pollLast(), nums.pollLast(), operations.pollLast()));
        while (!operations.isEmpty()){
            nums.addFirst(cal(nums.pollFirst(), nums.pollFirst(), operations.pollFirst()));
        }
        return nums.pop();
    }

    public int cal(int tmp2, int tmp1, char operation){
        if(operation=='+') return tmp1+tmp2;
        else if(operation=='-') return tmp2-tmp1;
        else if(operation=='*') return tmp1*tmp2;
        else return tmp1/tmp2;
    }

}
